package DynamicProgrammingPackage;

public class numSquares_ {
    public static void main(String[] args) {
        System.out.println(numSquares(12));
    }

    // 1. dp[j] 表示完全平方数和为j的最小数字量
    // 2. 递推公式: dp[j] = Math.min(dp[j],dp[j - nums[i]] + 1)
    // 3. 初始化: dp[0] = 0, dp[j] = Integer.maxValue
    // 4. 遍历: 无所谓排列, 且为完全背包问题, 先遍历物品后遍历背包 且背包正序遍历
    public static int numSquares(int n) {
        int[] dp = new int[n / 2 + 1];
        dp[0] = 0;
        for (int i = 1; i < dp.length; i++) {
            dp[i] = Integer.MAX_VALUE;
        }
        for (int i = 1; i < n / 2; i++) {
            for (int j = 1; j <= n / 2; j++) {
                if (i * i <= j)
                dp[j] = Math.min(dp[j],dp[j - i*i] + 1);
            }
        }
        return dp[n / 2];
    }
}
